<TITLE>prob012: nonogram</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob012: nonogram</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> 
          <B>Gary Duncan</B>
          <ADDRESS><a href="mailto:gduncan@cs.strath.ac.uk">
          gduncan@cs.strath.ac.uk</a></ADDRESS>
     <TD> and     
     <TD ALIGN=LEFT> <A HREF="http://www.dcs.st-and.ac.uk/~ipg/">
          <B>Ian Gent</B></A>
          <ADDRESS><a href="mailto:ipg@dcs.st-and.ac.uk">
          ipg@dcs.st-and.ac.uk</a></ADDRESS>

</TABLE>
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Summary </H3>

Nonograms are a popular puzzle, which goes by different names in different
countries.  Solvers have to shade in squares in a grid so that blocks 
of consecutive shaded squares satisfy constraints given for each row and 
column. Constraints typically indicate the sequence of shaded blocks
(e.g. 3,1,2 means that there is a block of 3, then a gap of unspecified
size, a block of length 1, another gap, and then a block of length 2).

<P>

The puzzle appears regularly in the Sunday Telegraph (UK) and 
irregularly in Games Magazine (US).  It is also very popular in Japan.
Our experience is that most puzzles set for humans can be solved by 
constraint propagation alone.  However the second solution problem:
i.e. find a second solution to a puzzle given a first one, is known to 
be NP-complete.  The regular puzzle must be also, but we have not seen 
a reference that confirms that fact.

<P>

We hope to give further details, including references, URL's and 
details of how the problem can be solved using constraint techniques, 
in the very near future.   In the meantime, if you are interested
in further details, contact Ian Gent, ipg@cs.strath.ac.uk


<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.



